#include <iostream>

using namespace std;
typedef unsigned long long BIG;

BIG routes1 (const uint_fast8_t x,const uint_fast8_t y)
{
	if(x == 0 || y == 0) return 1;
	else return routes1(x-1,y) + routes1(x,y-1);
}

BIG routes2 (const uint_fast8_t x,const uint_fast8_t y)
{
	BIG cache[x+1][y+1];
	for(int i=0;i<=x;i++) cache[i][y] = 1;
	for(int i=0;i<=y;i++) cache[x][i] = 1;

	for(int i=y-1;i>=0;i--)
		for(int j=x-1;j>=0;j--)
			cache[j][i] = cache[j+1][i] + cache[j][i+1];

	return cache[0][0];
}

BIG routes3 (const uint_fast8_t x,const uint_fast8_t y)
{
	BIG cache[x+1];
	for(int i=0;i<=x;i++) cache[i] = 1;

	for(int i=y-1;i>=0;i--)
		for(int j=x-1;j>=0;j--)
			cache[j] = cache[j+1] + cache[j];

	return cache[0];
}

int main()
{
	//cout << routes1(20,20) << endl;
	//cout << routes2(20,20) << endl;
	cout << routes3(20,20) << endl;

	return 0;
}


/// n!/r!(n-r)!
/// r = the number of rows (20), n = 2r (40).
/// It can be simplifed to 40!/20!^2.


//40 choose 20 = 137 846 528 820
